package first.codeTop.byteDance;

/**
 * @ClassName Leetcode200
 * @description:
 * @author: 荣燊
 * @create: 2021-07-27 17:29
 **/
public class Leetcode200 {
    // 岛屿数量

    public static void main(String[] args) {

    }

    // 我们可以扫描整个二维网格。如果一个位置为1，则以其为起始节点开始进行深度优先搜索
    // 在深度优先搜索的过程中，每个搜索到的1都会被重新标记为0
    public static int numIslands(char[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        int res = 0;
        for (int i=0; i<row; i++) {
            for (int j=0; j<column; j++) {
                if (grid[i][j] == '1') {
                    ++res;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    // 一个指针是在行中左右移动，一个指针在列中上下移动
    static void dfs(char[][] grid, int i, int j) {
        int row = grid.length;
        int column = grid[0].length;
        if (i<0 || j<0 || i>=row || j>= column || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
}
